import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public abstract class AbstractGraph<V> implements Graph<V> {

    protected List<V> vertices = new ArrayList<>();//顶点集
    protected List<List<Edge>> neighbors = new ArrayList<>();//邻接边线性表存储边集

    /**
     * 构造方法
     */
    protected AbstractGraph() {
    }

    protected AbstractGraph(V[] vertices, int[][] edges) {
        for (V vertex : vertices) {
            addVertex(vertex); //遍历顶点数组，将顶点加到顶点集中
        }
        createAdjacencyLists(edges, vertices.length);//创建邻接边线性表
    }

    protected AbstractGraph(List<V> vertices, List<Edge> edges) {
        for (V vertex : vertices) {
            addVertex(vertex);
        }
        createAdjacencyLists(edges, vertices.size());
    }

    /**
     * 创建邻接边线性表
     */
    private void createAdjacencyLists(int[][] edges, int numberOfVertex) {
        for (int[] edge : edges) {
            addEdge(edge[0], edge[1]);
        }
    }

    private void createAdjacencyLists(List<Edge> edges, int numberOfVertex) {
        for (Edge edge : edges) {
            addEdge(edge);
        }
    }

    /**
     * 返回图中的顶点数
     */
    @Override
    public int getSize() {
        return vertices.size();
    }

    /**
     * 返回图中的顶点（列表）
     */
    @Override
    public List<V> getVertices() {
        return vertices;
    }

    /**
     * 返回指定下标的顶点
     */
    @Override
    public V getVertex(int index) {
        return vertices.get(index);
    }

    /**
     * 返回指定顶点的下标
     */
    @Override
    public int getIndex(V v) {
        return vertices.indexOf(v);
    }

    /**
     * 返回指定下标顶点的邻居（列表）----邻接顶点线性表的元素
     */
    @Override
    public List<Integer> getNeighbors(int index) {
        ArrayList<Integer> result = new ArrayList<>();
        for (Edge e : neighbors.get(index)) {
            result.add(e.v);
        }
        return result;
    }

    /**
     * 返回指定下标的度
     */
    @Override
    public int getDegree(int index) {
        return neighbors.get(index).size();
    }

    /**
     * 打印边
     */
    @Override
    public void printEdges() {
        for (int i = 0; i < vertices.size(); i++) {
            System.out.print(vertices.get(i) + "(" + i + "):");
            for (Edge e : neighbors.get(i)) {
                System.out.print("(" + e.u + "," + e.v + ") ");
            }
            System.out.println();
        }
    }

    /**
     * 清除图
     */
    @Override
    public void clear() {
        vertices.clear();
        neighbors.clear();
    }

    /**
     * 增加顶点
     */
    @Override
    public boolean addVertex(V v) {
        if (vertices.contains(v)) {
            return false;
        } else {
            vertices.add(v);
            neighbors.add(new ArrayList<>());
            return true;
        }
    }

    /**
     * 增加边
     */
    @Override
    public boolean addEdge(int u, int v) {
        return addEdge(new Edge(u, v));
    }

    public boolean addEdge(Edge e) {
        if (e.u < 0 || e.u > vertices.size() - 1) {
            throw new IllegalArgumentException("no such index:" + e.u);
        }
        if (e.v < 0 || e.v > vertices.size() - 1) {
            throw new IllegalArgumentException("no such index:" + e.v);
        }
        if (neighbors.get(e.u).contains(e)) {
            return false;
        } else {
            neighbors.get(e.u).add(e);
            return true;
        }
    }

    /**
     * 得到一个从指定下标v开始的深度优先搜索树
     */
    @Override
    public Tree dfs(int v) {
        int root = v;
        int[] parent = new int[vertices.size()];
        List<Integer> searchOrder = new ArrayList<>();
        //创建追踪数组
        boolean[] isVisited = new boolean[vertices.size()];//检查该节点是否已被访问
        for (int i = 0; i < vertices.size(); i++) {
            isVisited[i] = false;//初始化追踪数组
        }
        for (int i = 0; i < parent.length; i++) {
            parent[i] = -1;//初始化父节点数组
        }

        dfs(v, parent, searchOrder, isVisited);

        return new Tree(root, parent, searchOrder);
    }

    public void dfs(int v, int[] parent, List<Integer> searchOrder, boolean[] isVisited) {
        //遍历到下标为v的节点
        searchOrder.add(v);
        isVisited[v] = true;

        for (Integer w : getNeighbors(v)) {
            if (!isVisited[w]) {
                parent[w] = v;
                dfs(w, parent, searchOrder, isVisited);//递归搜索w的邻居节点
            }
        }
    }

    /**
     * 得到一个从指定下标v开始的广度优先搜索树
     */
    @Override
    public Tree bfs(int v) {
        int root = v;
        int[] parent = new int[vertices.size()];
        List<Integer> searchOrder = new ArrayList<>();

        boolean[] isVisited = new boolean[vertices.size()];//检查该节点是否已被访问
        for (int i = 0; i < vertices.size(); i++) {
            isVisited[i] = false;//初始化追踪数组
        }
        //初始化父节点数组
        Arrays.fill(parent, -1);

        LinkedList<Integer> queue = new LinkedList<>();//创建一个空的队列
        //拜访根节点
        queue.offer(v);
        isVisited[v] = true;

        //循环和队列实现按照由内到外的顺序 广度优先搜索
        while (!queue.isEmpty()) {
            Integer u = queue.poll();
            searchOrder.add(u);
            for (Integer w : getNeighbors(u)) {
                if (!isVisited[w]) {
                    queue.offer(w);
                    parent[w] = u;
                    isVisited[w] = true;
                }
            }
        }

        return new Tree(root, parent, searchOrder);
    }

    /**
     * 定义内部类：Edge,
     * 将边定义为对象
     * 根据首尾顶点下标创建
     */
    public static class Edge {
        public int u;
        public int v;

        public Edge(int u, int v) {
            this.u = u;
            this.v = v;
        }

        public boolean equals(Edge e) {
            return u == e.u && v == e.v;
        }
    }

    /**
     * 定义内部类：Tree,
     * 描述节点的父子关系
     * 根据根、边、搜索顺序创建
     */
    public class Tree {
        private int root;
        private int[] parent;
        private List<Integer> searchOrder;

        public Tree(int root, int[] parent, List<Integer> searchOrder) {
            this.root = root;
            this.parent = parent;
            this.searchOrder = searchOrder;
        }

        public int getRoot() {
            return root;
        }

        public int getParent(int index) {
            return parent[index];
        }

        public List<Integer> getSearchOrder() {
            return searchOrder;
        }

        //返回搜索到的顶点个数
        public int getNumberOfVerticesFound() {
            return searchOrder.size();
        }

        //返回一个从指定下标的顶点到根节点的顶点线性表(存储节点的列表)
        public List<V> getPath(int index) {
            ArrayList<V> path = new ArrayList<>();

            while (index != -1) {
                path.add(vertices.get(index));
                index = parent[index];
            }
            return path;
        }

        //显示一条从根节点到指定节点的路径(打印点)
        public void printPath(int index) {
            List<V> path = getPath(index);
            System.out.println("A path from " + vertices.get(root) +
                    "to " + vertices.get(index) + ":");

            for (int i = path.size() - 1; i >= 0; i--) {
                System.out.print(path.get(i) + " ");
            }
        }

        //显示树的根节点和所有的边(打印根节点和边)
        public void printTree() {
            System.out.println("Root is:" + vertices.get(root));
            System.out.print("Edges is:");

            for (int i = 0; i < parent.length; i++) {
                if (parent[i] != -1) {
                    System.out.print("(" + vertices.get(parent[i]) + "," +
                            vertices.get(i) + ") ");
                }
            }
        }
    }
}